package com.touni.utils;

/**
 * @ClassName : CalDemo
 * @Description :
 * @Author : lwq
 * @Date: 2021-04-22 09:30
 */
public class CalDemo {

    public static void main(String[] args) {
        /*int[] arr = {1,5,9,48,56,96,120};
        int i = binarySearchV2(arr, 0,arr.length-1,48);
        System.out.println(i);*/
/*        int[] arr = {12,89,45,8,6,23,96,41,83,76,89};
        int[] ints = bubbleSort(arr);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(arr[i] + " ");
        }*/
        int[] arr = {6,2,5,6,8,9};
        int[] ints = insertSort(arr);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]+" ");
        }
    }






    //插入排序法   在一个已经排好序的数组中插入一个数
    public static int[] insertSort(int[] arr){
        // 6 5 9 10 58 96
        for (int i = 1; i < arr.length; i++) {
            int needInsert = arr[i];
            int index = i-1;
            //要插入的数比被插入的数小  需要将被插入的数放到被插入数前面
            while (index >= 0 && needInsert < arr[index]){
                //数组向后推移
                arr[index+1] = arr[index];
                index--;
            }
            arr[index + 1] = needInsert;
        }
        return arr;
    }





    //冒泡排序
    public static int[] bubbleSort(int[] arr){
        //外层控制循环次数
        for (int i = 0; i < arr.length; i++){
            //内层控制交换
            for (int j = 0; j < arr.length -1 -i;j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

    //二分查找  -----非递归方式  每次用中间的跟两边比较
    public static int binarySearch(int[] arr,int a){
        int low = 0;
        int high = arr.length-1;
        int mid;
        while (low <= high){
            mid = (low + high)/2;
            if (arr[mid] > a){
                high = mid - 1;
            }else if (arr[mid] < a){
                low = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    //二分查找 ---递归形式调用
    public static int binarySearchV2(int[] arr,int low,int high,int key){
        int mid = (low + high)/2;
        if (low > high){
            return -1;
        }
        if (arr[mid] > key){
            high = mid -1;
            return binarySearchV2(arr, low, high, key);
        } else if (arr[mid] < key){
            low = mid + 1;
            return binarySearchV2(arr, low, high, key);
        } else {
            return mid;
        }
    }

}
